package cn.hughie.str;

import utils.SortUtils;

import java.util.Arrays;

/**
 * @Author yuh
 * @Date Created in 上午9:08 2018/5/19
 * @Description 字符串三向快速排序
 */
public class QuickSort3Str {

    private static int charAt(String str, int d) {
        if (d < str.length()) {
            return str.charAt(d);
        } else {
            return -1;
        }
    }

    public static void sort(String[] strs) {
        threeWays(strs, 0, strs.length - 1, 0);
    }

    /**
     * 三向切分
     *
     * @param strs
     * @param l    左索引
     * @param r    右索引
     * @param d    第几个字符
     */
    private static void threeWays(String[] strs, int l, int r, int d) {

        if (l >= r) {
            return;
        }
        int lt = l;
        int i = lt + 1;
        int gt = r + 1;
        int e = charAt(strs[l], d);

        while (i < gt) {
            int tmp = charAt(strs[i], d);
            if (tmp < e) {
                SortUtils.swap(strs, ++lt, i++);
            } else if (tmp > e) {
                SortUtils.swap(strs, --gt, i);
            } else {
                i++;
            }
        }

        SortUtils.swap(strs, l, lt);
        threeWays(strs, l, lt - 1, d);
        if (e > 0) {
            threeWays(strs, lt, gt - 1, d + 1);
        }
        threeWays(strs, gt, r, d);
    }

    public static void main(String[] args) {
        String[] strs = {"♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️511111111111112", "♥️179217492743092", "♥️1", "♦️2","♥️542380482349", "♥️1", "♥️1", "♦️2","♥️5", "♥️1", "♥️1", "♦️2","♥️5", "♥️1", "♥️1", "♦️2","♥️5", "♥️1", "♥️1", "♦️2","♥️5", "♥️1", "♥️1", "♦️2","♥️5", "♥️1", "♥️1", "♦️2","♥️5", "♥️1", "♥️1", "♦️2","♥️5", "♥️1", "♥️1", "♦️2","♥️5", "♥️1", "♥️1", "♦️2","♥️5", "♥️1", "♥️1", "♦️2"};
        long l = System.currentTimeMillis();
        //sort(strs);
        Arrays.sort(strs);
        System.out.println(System.currentTimeMillis()-l);
        System.out.println(Arrays.toString(strs));
    }
}
